#2018年国赛-程序设计题 迷宫与陷阱
from collections import deque
n, K = map(int, input().split())
maze = [list(input().strip()) for _ in range(n)]
# 用于表示在位置 (x, y) 且剩余无敌步数为 k 时，是否已经被访问过
vis =[[[False] * (K + 1) for _ in range(n)] for _ in range(n)]
dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]

q = deque()
# 初始化起点
q.append((0, 0, 0, 0))
vis[0][0][0] = True
found = False
ans = -1

while q:
    x, y, rest_k, step = q.popleft()
    if x == n - 1 and y == n - 1:  # 终点
        ans = step
        found = True
        break
    for i, j in dir:
        nx, ny = x + i, y + j
        if 0 <= nx < n and 0 <= ny < n:
            now = maze[nx][ny]
            # 以下所有continue都能跳出当前for循环
            # 遇到墙
            if now == '#':
                continue
            # 遇到道具
            if now == '%':
                rest = K
                maze[nx][ny] = '.'
                if not vis[nx][ny][rest]:
                    vis[nx][ny][rest] = True
                    q.append((nx, ny, rest, step + 1))
                continue
            # 遇到陷阱
            if now == 'X':
                if rest_k == 0:
                    continue
                else:
                    rest = rest_k - 1
            # 遇到.或者被经过的%
            else:
                rest = rest_k - 1 if rest_k > 0 else 0
            if not vis[nx][ny][rest]:
                vis[nx][ny][rest] = True
                q.append((nx, ny, rest, step + 1))

print(ans if found else -1)
